/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
/*
创建一个伪头节点head，指针p指向头节点
用h1和h2分别指向两个排序链表的第一个结点
如果h1的value小于等于h2的value，就将h1指向的结点连接到p的next上，h1继续向后走
否则就让h2的结点到P的next上，h2向后走
以上步骤重复，直到h1或者h2指针指向null
将剩下的结点连接到p后面
*/
class Solution {
public:
    ListNode* Merge(ListNode* head1, ListNode* head2) {
        ListNode *head3=new ListNode(-1);
        ListNode *p=head3;
        while(head1&&head2)
        {
            if(head1->val<=head2->val)
            {
               p->next=head1;
               head1=head1->next;
            }else
            {
               p->next=head2;
                head2=head2->next;
            }
            p=p->next;
        }
        if(head1)
        {
           p->next=head1;
        }
        else
        {
            p->next=head2;
        }
        return head3->next;
    }
};